package com.LeeCode;

import java.util.Arrays;

/**
 * 两个数组间的距离值
 */

public class Code1385 {
    public static void main(String[] args) {
        int[] arr1 = {2, 1, 100, 3};
        int[] arr2 = {-5, -2, 10, -3, 7};
        int d = 6;

        System.out.println(new Code1385().findTheDistanceValue(arr1, arr2, d));
    }

    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        Arrays.sort(arr2);
        int ans = 0;
        for (int i = 0; i < arr1.length; i++) {
            int pos = lowerBound(arr2, arr1[i] - d);
            if (pos == arr2.length || arr2[pos] > arr1[i] + d)
                ans++;
        }
        return ans;
    }

    private int lowerBound(int[] arr, int target) {
        int left = -1, right = arr.length, mid;
        while (left + 1 < right) {
            mid = left + (right - left) / 2;
            if (arr[mid] >= target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
